package my;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class BSTIterator {
	private List<Integer> list = new ArrayList<Integer>();
	private Iterator<Integer> it = list.iterator();
	private boolean hasNext = false;
	private int next = 0;

	public static void main(String[] args) {
		Object[] arrTree = new Object[] { 15, 9, 20, 7, 11, 17, 25, 4, 8, '#' };
		TreeNode root = StackSolution.arrayToTree(arrTree);
		BSTIterator i = new BSTIterator(root);
		while (i.hasNext()) {
			System.out.println(i.next());
		}
	}

	public BSTIterator(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		if (root == null)
			return;
		TreeNode pRoot = root;
		while (pRoot != null || stack.size() > 0) {
			while (pRoot != null) {
				stack.push(pRoot);
				pRoot = pRoot.left;
			}
			pRoot = stack.pop();
			list.add(pRoot.val);
			pRoot = pRoot.right;
		}
		it = list.iterator();
	}

	/** @return whether we have a next smallest number */
	public boolean hasNext() {
		hasNext = it.hasNext();
		return hasNext;
	}

	/** @return the next smallest number */
	public int next() {
		next = it.next();
		return next;
	}
}
